{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check Knight Tour Configuration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #array #matrix #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #数组 #矩阵 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkValidGrid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查骑士巡视方案"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>骑士在一张 <code>n x n</code> 的棋盘上巡视。在&nbsp;<strong>有效&nbsp;</strong>的巡视方案中，骑士会从棋盘的 <strong>左上角</strong> 出发，并且访问棋盘上的每个格子 <strong>恰好一次</strong> 。</p>\n",
    "\n",
    "<p>给你一个 <code>n x n</code> 的整数矩阵 <code>grid</code> ，由范围 <code>[0, n * n - 1]</code> 内的不同整数组成，其中 <code>grid[row][col]</code> 表示单元格 <code>(row, col)</code> 是骑士访问的第 <code>grid[row][col]</code> 个单元格。骑士的行动是从下标 <strong>0</strong> 开始的。</p>\n",
    "\n",
    "<p>如果 <code>grid</code> 表示了骑士的有效巡视方案，返回 <code>true</code>；否则返回 <code>false</code>。</p>\n",
    "\n",
    "<p><strong>注意</strong>，骑士行动时可以垂直移动两个格子且水平移动一个格子，或水平移动两个格子且垂直移动一个格子。下图展示了骑士从某个格子出发可能的八种行动路线。<br />\n",
    "<img alt=\"\" src=\"https://pic.leetcode.cn/1694590028-CTMBQL-image.png\" style=\"width: 350px; height: 350px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://pic.leetcode.cn/1694590044-AmhkRb-image.png\" style=\"width: 251px; height: 251px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>grid 如上图所示，可以证明这是一个有效的巡视方案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://pic.leetcode.cn/1694590057-FIMBAG-image.png\" style=\"width: 151px; height: 151px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>grid = [[0,3,6],[5,8,1],[2,7,4]]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>grid 如上图所示，考虑到骑士第 7 次行动后的位置，第 8 次行动是无效的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == grid.length == grid[i].length</code></li>\n",
    "\t<li><code>3 &lt;= n &lt;= 7</code></li>\n",
    "\t<li><code>0 &lt;= grid[row][col] &lt; n * n</code></li>\n",
    "\t<li><code>grid</code> 中的所有整数 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-knight-tour-configuration](https://leetcode.cn/problems/check-knight-tour-configuration/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-knight-tour-configuration](https://leetcode.cn/problems/check-knight-tour-configuration/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,11,16,5,20],[17,4,19,10,15],[12,1,8,21,6],[3,18,23,14,9],[24,13,2,7,22]]', '[[0,3,6],[5,8,1],[2,7,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n, 1):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        # 暴力遍历所有点\n",
    "        n, dest = len(grid), [0,0]\n",
    "        for next_p in range(1,n*n):\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]==next_p:\n",
    "                        if abs(dest[0]-i)+abs(dest[1]-j)==3:\n",
    "                            dest[0], dest[1]=i, j\n",
    "                        else:\n",
    "                            return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        coordinate = {}\n",
    "        if grid[0][0] !=0:\n",
    "            return False\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[i])):\n",
    "                coordinate[grid[i][j]] = [i,j]\n",
    "        max_num=len(grid)*len(grid)-1\n",
    "        for s in range(max_num):\n",
    "            x1 = coordinate[s][0]\n",
    "            y1= coordinate[s][1]\n",
    "            x2 = coordinate[s+1][0]\n",
    "            y2 = coordinate[s+1][1]\n",
    "            if abs(x1-x2) !=1 or abs(y1-y2)!=2:\n",
    "                if abs(x1-x2) !=2 or abs(y1-y2)!=1:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        dire=[(-1,-2),(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2)]\n",
    "        x,y=0,0\n",
    "        n=len(grid)\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        count=0\n",
    "        for z in range(n**2-1):\n",
    "            if count<z:\n",
    "                break\n",
    "            for i,j in dire:\n",
    "                dx=x+i\n",
    "                dy=y+j\n",
    "                if -1<dx<n and -1<dy<n and grid[dx][dy]==z+1:\n",
    "                    x,y=dx,dy\n",
    "                    count+=1\n",
    "                    continue\n",
    "        return count==(n**2-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]: return False # 特判起点\n",
    "        n = len(grid) # 矩阵长度\n",
    "        dir = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]] # 8个方向的坐标增量\n",
    "        x = y = 0 # 当前位置\n",
    "        for target in range(1, n * n): # 目标值\n",
    "            for dx, dy in dir: # 遍历8个方向\n",
    "                xi, yi = x + dx, y + dy # 下一步的位置\n",
    "                if 0 <= xi < n and 0 <= yi < n and grid[xi][yi] == target: # 下一步的位置没有越界，并且等于目标值\n",
    "                    x, y = xi, yi # 走到该位置\n",
    "                    break # 跳出循环\n",
    "            else: return False # 如果搜索完8个方向都没有匹配到目标值，按照题意，应当返回false\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        n = len(grid)\n",
    "        cur = 0\n",
    "        row = col = 0\n",
    "        ans = False\n",
    "        if grid[0][0]:\n",
    "            return ans\n",
    "        dir = [[-2, -1], [-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2]]\n",
    "        d = 0\n",
    "        while cur < n * n and d < len(dir):\n",
    "            \n",
    "            new_r, new_c = row + dir[d][0], col + dir[d][1]\n",
    "            if new_r >= 0 and new_r < n and new_c >= 0 and new_c < n and grid[new_r][new_c] == cur+1:\n",
    "                cur += 1\n",
    "                row, col = new_r, new_c\n",
    "                d = 0\n",
    "                continue\n",
    "            d += 1    \n",
    "        return cur == n * n - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        n=len(grid)\n",
    "        ci,cj=(0,0)\n",
    "        for i in range(1,n*n):\n",
    "            found=False\n",
    "            for x,y in [(-2,1),(-2,-1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]:\n",
    "                ni,nj=ci+x,cj+y\n",
    "                if ni<0 or ni>=n or nj<0 or nj>=n:\n",
    "                    continue\n",
    "                if grid[ni][nj]==i:\n",
    "                    found=True\n",
    "                    ci,cj=(ni,nj)\n",
    "                    break\n",
    "            if not found:\n",
    "                return False\n",
    "            \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        \"\"\"\n",
    "        生成一个列表actions: List[Tuple(int,int)]\n",
    "        actions[i] = （r,c）:表示第i步走到了第r行第c列。\n",
    "        我们只需要检测所有的actions[i],actions[i+1]是否合法即可。\n",
    "        \"\"\"\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        M, N = len(grid), len(grid[0])\n",
    "        actions: List[Tuple[int,int]] = [(0,0)]*(M*N)\n",
    "        for r in range(M):\n",
    "            for c in range(N):\n",
    "                actions[grid[r][c]] = (r,c)\n",
    "        \n",
    "        for cur_act, next_act in zip(actions[:-1], actions[1:]):\n",
    "            r0,c0 = cur_act\n",
    "            r1,c1 = next_act\n",
    "            if (r0-r1, c0-c1) not in [(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)]:\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        locals = collections.defaultdict(list)\n",
    "        n = len(grid)\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                locals[grid[i][j]]+=[i,j]\n",
    "                \n",
    "        local = locals[0]\n",
    "        if local!=[0,0]:\n",
    "            return False\n",
    "\n",
    "        for i in range(1, n*n):\n",
    "            if abs(locals[i][0] - local[0]) + abs(locals[i][1] - local[1]) != 3  or abs(locals[i][0] - local[0])==0:\n",
    "                return False\n",
    "            else:\n",
    "                local = locals[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        data={}\n",
    "        n=len(grid)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                data[grid[i][j]]=[i,j]\n",
    "        \n",
    "        last=[]\n",
    "        for i in range(n*n):\n",
    "            if i==0:\n",
    "                if data[i]==[0,0]:\n",
    "                    last=[0,0]\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                tmp=abs(last[0]-data[i][0])*abs(last[1]-data[i][1])\n",
    "                if tmp!=2:\n",
    "                    return False\n",
    "                else:\n",
    "                    last=data[i]\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def check(a, b):\n",
    "            x = b[0] - a[0]\n",
    "            y = b[1] - a[1]\n",
    "            if abs(x) == 2 and abs(y) == 1:\n",
    "                return True\n",
    "            if abs(x) == 1 and abs(y) == 2:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        steps = [[0, 0]] * (n * n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                steps[grid[i][j]] = [i, j]\n",
    "        last = steps[0]\n",
    "        for i in range(1, n*n):\n",
    "            g = steps[i]\n",
    "            if not check(last, g):\n",
    "                return False\n",
    "            last = g\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        pos = [None] * (n * n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                pos[grid[i][j]] = (i, j)\n",
    "        for (x1, y1), (x2, y2) in pairwise(pos):\n",
    "            dx, dy = abs(x1 - x2), abs(y1 - y2)\n",
    "            ok = (dx == 1 and dy == 2) or (dx == 2 and dy == 1)\n",
    "            if not ok:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        pos = [None] * (n * n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                pos[grid[i][j]] = (i, j)\n",
    "        for (x1, y1), (x2, y2) in pairwise(pos):\n",
    "            dx, dy = abs(x1 - x2), abs(y1 - y2)\n",
    "            ok = (dx == 1 and dy == 2) or (dx == 2 and dy == 1)\n",
    "            if not ok:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        m = len(grid)\n",
    "        map={}\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                map[grid[i][j]]=[i,j]\n",
    "        for i in range(1,m**2):\n",
    "            if abs(map[i][0]-map[i-1][0])==2:\n",
    "                if not abs(map[i][1]-map[i-1][1])==1:\n",
    "                    return False\n",
    "            elif abs(map[i][0]-map[i-1][0])==1:\n",
    "                if not abs(map[i][1]-map[i-1][1])==2:\n",
    "                    return False\n",
    "            else: return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        # 这里是二维数组数组的定义\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "\n",
    "        # 将所有的（x，y）存入到indices中\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                # temp = grid[i][j]\n",
    "                # indices[temp][0] = i\n",
    "                # indices[temp][1] = j\n",
    "                # 上面的代码可以简单写\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        \n",
    "        # 对indices数组进行遍历\n",
    "        for i in range(1, n * n, 1):\n",
    "            if abs(indices[i][0]-indices[i-1][0]) * abs(indices[i][1]-indices[i-1][1]) != 2 :\n",
    "                return False   \n",
    "        # 上述全部遍历完成之后\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        n = len(grid)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                d[grid[i][j]] = [i, j]\n",
    "        for i in grid:\n",
    "            print(i)\n",
    "        if grid[0][0]:\n",
    "            return False\n",
    "        for i in range(1, n**2):\n",
    "            a1 = abs(d[i][0]-d[i-1][0])\n",
    "            a2 = abs(d[i][1]-d[i-1][1])\n",
    "            if not a1 or not a2 or a1 + a2 != 3:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "#         n, s = len(grid), 0\n",
    "#         v = [[0] * n for _ in n]\n",
    "#         a = [-2, -1, 1, 2, -2, -1, 1, 2]\n",
    "#         b = [1, 2, 2, 1, -1, -2, -2, -1]\n",
    "#         def solve(x, y):\n",
    "#             v[x][y] = 1\n",
    "#             grid[x][y] = \n",
    "#             for i, j in zip(a, b):\n",
    "#                 x1, y1 = x + i, y + j\n",
    "#                 if 0 <= x1 < n and 0 <= y1 < n and not \n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        d = [None] * n * n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                d[grid[i][j]] = (i, j)\n",
    "        for i in range(1, n*n):\n",
    "            x =  abs(d[i][0] - d[i-1][0])\n",
    "            y =  abs(d[i][1] - d[i-1][1])\n",
    "            if x + y != 3 or abs(x - y) != 1:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        dirs = [[-1, 2], [1, 2], [1, -2], [-1, -2], [2, 1], [2, -1], [-2, -1], [-2, 1]]\n",
    "        count = 0\n",
    "        cur = [0, 0]\n",
    "        while count < n * n - 1:\n",
    "            check = False\n",
    "            for d in dirs:\n",
    "                temp_i = cur[0] + d[0]\n",
    "                temp_j = cur[1] + d[1]\n",
    "                if 0 <= temp_i < n and 0 <= temp_j < n:\n",
    "                    if grid[temp_i][temp_j] == count + 1:\n",
    "                        check = True\n",
    "                        cur = [temp_i, temp_j]\n",
    "                        count += 1\n",
    "                        break\n",
    "            if not check:\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n, 1):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        n=len(grid)\n",
    "        indices=[[] for _ in range(n*n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]]=[i,j]\n",
    "        for i in range(1,n*n):\n",
    "            dx=abs(indices[i][0]-indices[i-1][0])\n",
    "            dy=abs(indices[i][1]-indices[i-1][1])\n",
    "            if dx*dy!=2:return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "      # 从左上角出发\n",
    "      if grid[0][0]:\n",
    "        return False\n",
    "      n = len(grid)\n",
    "      # 用pos数组来记录每一个格子的坐标\n",
    "      pos = [0] * (n * n)\n",
    "      for i in range(n):\n",
    "        for j in range(n):\n",
    "          pos[grid[i][j]] = (i, j)\n",
    "      # 判断是不是走日字\n",
    "      for (a, b), (c, d) in pairwise(pos):\n",
    "        dx = abs(a - c)\n",
    "        dy = abs(b - d)\n",
    "        if (dx != 2 or dy != 1) and (dx != 1 or dy != 2):\n",
    "          return False\n",
    "      return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        hash_list = defaultdict(list)\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                hash_list[grid[row][col]] = [row, col]\n",
    "        if hash_list[0] != [0, 0]:\n",
    "            return False\n",
    "        possibility = [[2, 1], [2, -1], [1, 2], [1, -2], [-1, 2], [-1, -2], [-2, 1], [-2, -1]]\n",
    "        for index in range(1, len(grid) ** 2):\n",
    "            if [hash_list[index][0] - hash_list[index - 1][0], hash_list[index][1] - hash_list[index - 1][1]] not in possibility:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n, 1):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        locs=[[] for i in range(len(grid)**2)]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                locs[grid[i][j]]=[i,j]\n",
    "        for i in range(len(grid)**2-1):\n",
    "            nextloc=locs[i+1]\n",
    "            nowloc=locs[i]\n",
    "            if not (abs(nextloc[0]-nowloc[0])+abs(nextloc[1]-nowloc[1])==3):\n",
    "                return False\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        indices = [0] * len(grid) ** 2\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                indices[x] = (i, j)\n",
    "        x1, y1 = indices[0][0], indices[0][1]\n",
    "        for x2, y2 in indices[1:]:\n",
    "            dx = abs(x2 - x1)\n",
    "            dy = abs(y2 - y1)\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "            x1, y1 = x2, y2\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0: return False\n",
    "        n = len(grid)\n",
    "        pos = [None] * (n * n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                pos[grid[i][j]] = (i, j)\n",
    "        for i in range(1, len(pos)):\n",
    "            (x1, y1) = pos[i-1]\n",
    "            (x2, y2) = pos[i]\n",
    "            dx, dy = abs(x1 - x2), abs(y1 - y2)\n",
    "            ok = (dx == 1 and dy == 2) or (dx == 2 and dy == 1)\n",
    "            if not ok:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "      if grid[0][0] != 0:\n",
    "        return False\n",
    "      step = 0\n",
    "      n = len(grid)\n",
    "      row, col = 0, 0\n",
    "      while step < n * n - 1:\n",
    "        if 0 <= row + 1 <= n - 1 and 0 <= col + 2 <= n - 1 and grid[row + 1][col + 2] == step + 1:\n",
    "          row += 1\n",
    "          col += 2\n",
    "        elif 0 <= row + 2 <= n - 1 and 0 <= col + 1 <= n - 1 and grid[row + 2][col + 1] == step + 1:\n",
    "          row += 2\n",
    "          col += 1\n",
    "        elif 0 <= row - 1 <= n - 1 and 0 <= col - 2 <= n - 1 and grid[row - 1][col - 2] == step + 1:\n",
    "          row -= 1\n",
    "          col -= 2\n",
    "        elif 0 <= row - 2 <= n - 1 and 0 <= col - 1 <= n - 1 and grid[row - 2][col - 1] == step + 1:\n",
    "          row -= 2\n",
    "          col -= 1\n",
    "        elif 0 <= row + 1 <= n - 1 and 0 <= col - 2 <= n - 1 and grid[row + 1][col - 2] == step + 1:\n",
    "          row += 1\n",
    "          col -= 2\n",
    "        elif 0 <= row + 2 <= n - 1 and 0 <= col - 1 <= n - 1 and grid[row + 2][col - 1] == step + 1:\n",
    "          row += 2\n",
    "          col -= 1\n",
    "        elif 0 <= row - 1 <= n - 1 and 0 <= col + 2 <= n - 1 and grid[row - 1][col + 2] == step + 1:\n",
    "          row -= 1\n",
    "          col += 2\n",
    "        elif 0 <= row - 2 <= n - 1 and 0 <= col + 1 <= n - 1 and grid[row - 2][col + 1] == step + 1:\n",
    "          row -= 2\n",
    "          col += 1\n",
    "        else:\n",
    "          return False\n",
    "        step += 1\n",
    "      return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        dir = [[-2,-1], [-2,1], [-1,-2], [-1,2], [1,-2], [1,2], [2,-1], [2,1]]\n",
    "        i,j = 0,0\n",
    "        ans = 1\n",
    "        while i<n and j<n and ans<n*n:\n",
    "            cnt = False\n",
    "            for dx,dy in dir:\n",
    "                xi,yi=i+dx,j+dy\n",
    "                if n>xi>=0 and n>yi>=0 and grid[xi][yi] == ans:\n",
    "                    i,j=xi,yi\n",
    "                    ans += 1\n",
    "                    cnt = True\n",
    "                    break\n",
    "            if cnt:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        size = len(grid)\n",
    "        def judge(new_row, new_col, res):\n",
    "            if new_row >= 0 and new_row < size and new_col >= 0 and new_col < size:\n",
    "                res.append([new_row, new_col])\n",
    "        def available_grid(row, col):\n",
    "            available = []\n",
    "            for i in [2,-2]:\n",
    "                for j in [1,-1]:\n",
    "                    new_row = row + i\n",
    "                    new_col = col + j\n",
    "                    judge(new_row, new_col, available)\n",
    "                    new_row = row + j\n",
    "                    new_col = col + i\n",
    "                    judge(new_row, new_col, available)\n",
    "            return available\n",
    "        \n",
    "        index = 0\n",
    "        total = size * size\n",
    "        x = 0\n",
    "        y = 0\n",
    "        while index < total - 1:\n",
    "            flag = 0\n",
    "            jump = available_grid(x, y)\n",
    "            if jump:\n",
    "                for row, col in jump:\n",
    "                    if grid[row][col] == index + 1:\n",
    "                        index += 1\n",
    "                        flag = 1\n",
    "                        x = row\n",
    "                        y = col\n",
    "                        break\n",
    "            if flag:\n",
    "                continue\n",
    "            else:\n",
    "                print(f\"index = {index}\")\n",
    "                print(f\"x = {x}, y = {y}\")\n",
    "                return False\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        n = len(grid)\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        seq = [0] * n * n\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                seq[grid[i][j]] = i * n + j\n",
    "        x = y = 0\n",
    "        for i in range(1, n * n):\n",
    "            p = seq[i]\n",
    "            x2, y2 = p // n, p % n\n",
    "            # print(i, x, y, x2, y2)\n",
    "            if abs(x - x2) in (1, 2) and abs(y - y2) in (1, 2) and abs(x - x2) != abs(y - y2):\n",
    "                x, y = x2, y2\n",
    "            else:\n",
    "                \n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:return False\n",
    "        pos=[0,0]\n",
    "        cur=0\n",
    "        n=len(grid)\n",
    "        dir=[(2,1),(2,-1),(1,2),(1,-2),(-2,1),(-2,-1),(-1,2),(-1,-2)]\n",
    "        flag=True\n",
    "        while flag:\n",
    "            if cur==n*n-1:\n",
    "                return True\n",
    "            flag=False\n",
    "            for i,j in dir:\n",
    "                x,y=pos[0]+i,pos[1]+j\n",
    "                if 0<=x<n and 0<=y<n and grid[x][y]==cur+1:\n",
    "                    cur+=1\n",
    "                    pos=[x,y]\n",
    "                    flag=True\n",
    "                    break\n",
    "        return cur==n*n-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == n * n - 1:\n",
    "                    break\n",
    "                for x,y in [i-1,j-2],[i+1,j-2],[i-2,j-1],[i+2,j-1],[i-2,j+1],[i+2,j+1],[i-1,j+2],[i+1,j+2]:\n",
    "                    if 0 <= x < n and 0 <= y < n and grid[x][y] - grid[i][j] == 1:\n",
    "                        break\n",
    "                else:\n",
    "                    return False\n",
    "        return True \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        n = len(grid)\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "\n",
    "        q = [(0,0)]\n",
    "        level = 1\n",
    "        while q:\n",
    "            x,y = q[0]\n",
    "            q = []\n",
    "            for nx,ny in [(x-1,y-2),(x-2,y-1),(x-2,y+1),(x-1,y+2),\\\n",
    "                    (x+1,y+2),(x+2,y+1),(x+2,y-1),(x+1,y-2)]:\n",
    "                    if 0<=nx<n and 0<=ny<n and grid[nx][ny]==level:\n",
    "                        q.append((nx,ny))\n",
    "                        break\n",
    "            level += 1\n",
    "        \n",
    "        if level == n*n+1:\n",
    "            return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        \n",
    "        n = len(grid)\n",
    "        if n==3:\n",
    "            return False\n",
    "        \n",
    "        coord = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                coord[grid[i][j]] = (i, j)\n",
    "        \n",
    "        for i in range(1, n * n):\n",
    "            x1,y1 = coord[i]\n",
    "            x2,y2 = coord[i-1]\n",
    "            dx = abs(x1 - x2)\n",
    "            dy = abs(y1 - y2)\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        # 排序后 遍历 移动步伐\n",
    "        # 1.校验开头\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "\n",
    "        # 排序\n",
    "        allPos = {}\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, value in enumerate(row):\n",
    "                allPos[value] = (i, j)\n",
    "\n",
    "        n = len(grid)\n",
    "\n",
    "        tmp = allPos.pop(0)\n",
    "        preX = tmp[0]\n",
    "        preY = tmp[1]\n",
    "        for i in range(1, n * n):\n",
    "            cur = allPos.pop(i)\n",
    "            curX = cur[0]\n",
    "            curY = cur[1]\n",
    "            if (abs(curX - preX) == 1 and abs(curY - preY) == 2) or (abs(curX - preX) == 2 and abs(curY - preY) == 1):\n",
    "                preX = curX\n",
    "                preY = curY\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n):\n",
    "            dx = indices[i][0] - indices[i - 1][0]\n",
    "            dy = indices[i][1] - indices[i - 1][1]\n",
    "            if abs(dx * dy) != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False \n",
    "        index_dict = {}\n",
    "        rows, cols = len(grid), len(grid)\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                index_dict[grid[i][j]] = [i, j] \n",
    "\n",
    "        return self.isValid(index_dict)\n",
    "    \n",
    "    def isValid(self, index_dict: dict) -> bool:\n",
    "        directions = [[1, -2], [-1, -2], [1, 2], [-1, 2], \n",
    "                      [-2, 1], [-2, -1], [2, 1], [2, -1]]\n",
    "        for current_index in range(len(index_dict) - 1):\n",
    "            x_diff = index_dict[current_index + 1][0] - index_dict[current_index][0] \n",
    "            y_diff = index_dict[current_index + 1][1] - index_dict[current_index][1]\n",
    "            if [x_diff, y_diff] not in directions:\n",
    "                return False \n",
    "        return  True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        path = [[] for _ in range(m*n)]\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,pos in enumerate(row):\n",
    "                path[pos] = (i,j)\n",
    "        for i in range(1,m*n):\n",
    "            x1,y1 = path[i]\n",
    "            x2,y2 = path[i-1]\n",
    "            if (x1-x2 == 1 or x2-x1==1) and (y1-y2 == 2 or y2-y1==2):\n",
    "                continue\n",
    "            elif (x1-x2 == 2 or x2-x1==2) and (y1-y2 == 1 or y2-y1==1):\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        n=len(grid)\n",
    "        poss = [(0,0)]*(n*n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                poss[grid[i][j]]=(i,j)\n",
    "        if poss[0] != (0,0): return False\n",
    "        for i in range(n*n-1):\n",
    "            a = abs(poss[i][0]-poss[i+1][0])\n",
    "            b = abs(poss[i][1]-poss[i+1][1])\n",
    "            if a!=1:\n",
    "                a,b = b,a\n",
    "            if a!=1 or b!=2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        n = len(grid)\n",
    "        d = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                d[grid[i][j]] = [i, j]\n",
    "        for i in grid:\n",
    "            print(i)\n",
    "        if grid[0][0]:\n",
    "            return False\n",
    "        for i in range(1, n**2):\n",
    "            a1 = abs(d[i][0]-d[i-1][0])\n",
    "            a2 = abs(d[i][1]-d[i-1][1])\n",
    "            if a1 * a2 != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n ** 2)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n**2, 1):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if not grid[0][0] == 0:\n",
    "            return False\n",
    "        move = [[] for _ in range(len(grid) * len(grid[0]))]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                move[grid[i][j]] = [i, j]\n",
    "        for i in range(len(move) - 1):\n",
    "            if not (move[i][0] - move[i+1][0]) ** 2 + (move[i][1] - move[i+1][1]) ** 2 == 5:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        hash_list = defaultdict(list)\n",
    "        for row in range(len(grid)):\n",
    "            for col in range(len(grid[0])):\n",
    "                hash_list[grid[row][col]] = [row, col]\n",
    "        if hash_list[0] != [0, 0]:\n",
    "            return False\n",
    "\n",
    "        for _ in range(1, len(grid) ** 2):\n",
    "            if abs(hash_list[_][0] - hash_list[_ - 1][0]) * abs(hash_list[_][1] - hash_list[_ - 1][1]) != 2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        a=[[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]]\n",
    "        n=0\n",
    "        wei=[0,0]\n",
    "        while n<len(grid)*len(grid)-1:\n",
    "            A=n\n",
    "            for i in range(8):\n",
    "                aa=[x+y for x,y in zip(wei,a[i])]\n",
    "                if aa[0]>=0 and aa[1]>=0 and aa[0]<=len(grid)-1 and aa[1]<=len(grid)-1:\n",
    "                    if grid[aa[0]][aa[1]]==n+1:\n",
    "                        wei=[aa[0],aa[1]]\n",
    "                        n=n+1\n",
    "                        B=n\n",
    "                        break\n",
    "                    else:\n",
    "                     B=n\n",
    "            if A==B:\n",
    "                return False\n",
    "        if n  ==len(grid)*len(grid)-1:\n",
    "            return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:#骑士会从棋盘的 左上角 出发\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        print(indices)\n",
    "        for i in range(1, n * n, 1):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx *dy!=  2:  #不能加和==3，（0,3）\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        br, bc = 0, 0\n",
    "        if grid[br][bc] != 0:\n",
    "            return False\n",
    "        steps = [[1, 2], [-1, 2], [1, -2], [-1, -2], [2, 1], [2, -1], [-2, 1], [-2, -1]]\n",
    "        remain = m * n\n",
    "        while grid[br][bc] != -1:\n",
    "            # find next position\n",
    "            find_next = False\n",
    "            for x, y in steps:\n",
    "                nx = br + x\n",
    "                ny = bc + y\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == grid[br][bc] + 1:\n",
    "                    grid[br][bc] = -1\n",
    "                    br, bc = nx, ny\n",
    "                    find_next = True\n",
    "                    remain -= 1\n",
    "                    break\n",
    "            if not find_next:\n",
    "                break\n",
    "        return remain == 1 and grid[br][bc] != -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0: return False\n",
    "        \n",
    "        n = len(grid)\n",
    "        loc = [(0, 0)] * (n * n)\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                loc[grid[i][j]] = (i, j)\n",
    "        \n",
    "        for (x1, y1), (x2, y2) in pairwise(loc):\n",
    "            dx = abs(x1 - x2); dy = abs(y1 - y2)\n",
    "            if not (dx == 1 and dy == 2 or dx == 2 and dy == 1):\n",
    "                return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n, 1):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0]!=0:return False\n",
    "        pos=[0,0]\n",
    "        cur=0\n",
    "        n=len(grid)\n",
    "        dir=[(2,1),(2,-1),(1,2),(1,-2),(-2,1),(-2,-1),(-1,2),(-1,-2)]\n",
    "        flag=True\n",
    "        while flag:\n",
    "            if cur==n*n-1:\n",
    "                return True\n",
    "            flag=False\n",
    "            for i,j in dir:\n",
    "                x,y=pos[0]+i,pos[1]+j\n",
    "                if 0<=x<n and 0<=y<n and grid[x][y]==cur+1:\n",
    "                    cur+=1\n",
    "                    pos=[x,y]\n",
    "                    flag=True\n",
    "                    break\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        \n",
    "        n = len(grid)\n",
    "        if n==3:\n",
    "            return False\n",
    "        \n",
    "        coord = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                coord[grid[i][j]] = (i, j)\n",
    "        \n",
    "        for i in range(1, n * n):\n",
    "            x1,y1 = coord[i]\n",
    "            x2,y2 = coord[i-1]\n",
    "            dx = abs(x1 - x2)\n",
    "            dy = abs(y1 - y2)\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "@author:lzz\n",
    "@date:2023/9/13\n",
    "@introduction:None\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: list) -> bool:\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        if m == 1:return True\n",
    "        if  grid[0][0]:return False\n",
    "        val = 0\n",
    "        b, x, y, val = 0, 0, 0, 0\n",
    "        while val <= (m*m):\n",
    "            if val == m * m - 1 : return True\n",
    "            b, x, y, val = self.checkway(grid, x, y, val, m, n)\n",
    "            if b == -1:return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    def checkway(self, grid: list, x, y, val, m, n):\n",
    "        # 八种走法 上下左右四个方位延申出去各自两种\n",
    "\n",
    "\n",
    "        if x + 1 < m and y + 2 < n and grid[x + 1][y + 2] == val + 1:\n",
    "            return 1, x + 1, y + 2, val + 1\n",
    "        elif x + 1 < m and y - 2 >= 0 and grid[x + 1][y - 2] == val + 1:\n",
    "            return 1, x + 1, y - 2, val + 1\n",
    "        elif x + 2 < m and y + 1 < n and grid[x + 2][y + 1] == val + 1:\n",
    "            return 1, x + 2, y + 1, val + 1\n",
    "        elif x + 2 < m and y - 1 >= 0 and grid[x + 2][y - 1] == val + 1:\n",
    "            return 1, x + 2, y - 1, val + 1\n",
    "        elif x - 1 >= 0 and y - 2 >= 0 and grid[x - 1][y - 2] == val + 1:\n",
    "            return 1, x - 1, y - 2, val + 1\n",
    "        elif x - 1 >= 0 and y + 2 < n and grid[x - 1][y + 2] == val + 1:\n",
    "            return 1, x - 1, y + 2, val + 1\n",
    "        elif x - 2 >= 0 and y - 1 >= 0 and grid[x - 2][y - 1] == val + 1:\n",
    "            return 1, x - 2, y - 1, val + 1\n",
    "        elif x - 2 >= 0 and y + 1 < n and grid[x - 2][y + 1] == val + 1:\n",
    "            return 1, x - 2, y + 1, val + 1\n",
    "\n",
    "        return -1,-1,-1,-1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        def check(nxt):\n",
    "            pair = ((x+1,y+2), (x+2,y+1),\n",
    "                    (x+1,y-2), (x+2,y-1),\n",
    "                    (x-1,y+2), (x-2,y+1),\n",
    "                    (x-1,y-2), (x-2,y-1))\n",
    "\n",
    "            for dx, dy in pair:\n",
    "                if ((0 <= dx < n and 0 <= dy < n)\n",
    "                        and grid[dx][dy] == nxt):\n",
    "                    return dx, dy\n",
    "            return x,y\n",
    "        \n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        \n",
    "        n = len(grid)\n",
    "        x = y = 0\n",
    "        for num in range(1, n*n):\n",
    "            x1,y1 = check(num)\n",
    "            if x1 == x and y1 == y:\n",
    "                return False\n",
    "            x = x1\n",
    "            y = y1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        def bfs(x,y,c):\n",
    "            while c<t1*t2-1:\n",
    "                zz=0\n",
    "                for m,n in z:\n",
    "                    if 0<=x+m<t1 and 0<=y+n<t2 and grid[x+m][y+n]==c+1:\n",
    "                        x+=m\n",
    "                        y+=n\n",
    "                        c+=1\n",
    "                        zz=1\n",
    "                        break\n",
    "                    else:\n",
    "                        continue\n",
    "                if zz==0:\n",
    "                    return False\n",
    "            return True\n",
    "        if grid[0][0]!=0:\n",
    "            return False\n",
    "        t1,t2=len(grid),len(grid[0])\n",
    "        z=[[2,1],[2,-1],[1,2],[1,-2],[-1,2],[-1,-2],[-2,-1],[-2,1]]\n",
    "        for a in range(t1):\n",
    "            for b in range(t2):\n",
    "                if grid[a][b]==0:\n",
    "                    return (bfs(a,b,0))\n",
    "                    break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        arr = [[0, 0] for _ in range(n*n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                arr[grid[i][j]] = [i, j]\n",
    "        \n",
    "        for i in range(1, n*n):\n",
    "            row = abs(arr[i][0] - arr[i-1][0])\n",
    "            col = abs(arr[i][1] - arr[i-1][1])\n",
    "            if row-col not in [1, -1] or min(row, col) != 1:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        cnt =dict()\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,x in enumerate(row):\n",
    "                cnt[x]=(i,j)\n",
    "        m,n = len(grid),len(grid[0]) \n",
    "        if cnt[0]!=(0,0):\n",
    "            return False\n",
    "        ox,oy = cnt[0]\n",
    "        for i in range(1,m*n):\n",
    "            nx,ny =cnt[i]\n",
    "            dx =abs(ox-nx)\n",
    "            dy = abs(ny-oy)\n",
    "            print(dx,dy)\n",
    "            if dx==2 and dy ==1 or dx==1 and dy ==2:\n",
    "                ox,oy =nx,ny\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        for i in range(1, n * n, 1):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.steps=0\n",
    "\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        visited=[[0]*m for _ in range(n)]\n",
    "\n",
    "        def ifValid(i,j):\n",
    "            return 0<=i<m and 0<=j<n and visited[i][j]==0\n",
    "\n",
    "        def dfs(i,j,step):\n",
    "            if step==m*n:\n",
    "                return True\n",
    "            visited[i][j]=1\n",
    "            directs=([i+2,j-1],[i+1,j-2],[i-1,j-2],[i-2,j-1],[i-2,j+1],[i-1,j+2],[i+1,j+2],[i+2,j+1])\n",
    "            for direct in directs:\n",
    "                if ifValid(direct[0],direct[1]) and grid[direct[0]][direct[1]]==step:\n",
    "                    step+=1\n",
    "                    if dfs(direct[0],direct[1],step):\n",
    "                        return True\n",
    "                    step-=1\n",
    "            visited[i][j]=0\n",
    "            return False\n",
    "\n",
    "        return dfs(0,0,1)\n",
    "         \n",
    "\n",
    "\n",
    "\n",
    "# def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "#     n = len(grid)\n",
    "#     visited = [[False] * n for _ in range(n)]\n",
    "\n",
    "#     # 寻找起点位置\n",
    "#     start_row, start_col = 0, 0\n",
    "#     # 槽点，起点还要这样判断\n",
    "#     if grid[0][0] is not 0:\n",
    "#         return False\n",
    "#     for i in range(n):\n",
    "#         for j in range(n):\n",
    "#             if grid[i][j] == 0:\n",
    "#                 start_row, start_col = i, j\n",
    "#                 break\n",
    "\n",
    "#     # 检查是否存在有效的欧拉路径\n",
    "#     def dfs(row, col, count):\n",
    "#         nonlocal n\n",
    "#         visited[row][col] = True\n",
    "#         count += 1\n",
    "\n",
    "#         if count == n * n:\n",
    "#             return True\n",
    "\n",
    "#         directions = [(1, 2), (2, 1), (2, -1), (1, -2),\n",
    "#                     (-1, -2), (-2, -1), (-2, 1), (-1, 2)]\n",
    "#         for direction in directions:\n",
    "#             next_row = row + direction[0]\n",
    "#             next_col = col + direction[1]\n",
    "#             if (0 <= next_row < n and 0 <= next_col < n and\n",
    "#                     not visited[next_row][next_col] and\n",
    "#                     grid[next_row][next_col] == count and\n",
    "#                     dfs(next_row, next_col, count)):\n",
    "#                 return True\n",
    "\n",
    "#         visited[row][col] = False\n",
    "#         count -= 1\n",
    "\n",
    "#         return False\n",
    "\n",
    "#     return dfs(start_row, start_col, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        \n",
    "        # all directions:(base [x,y])\n",
    "        # [x+1, y+2],[x+2,y+1],[x+2,y-1],[x+1,y-2]\n",
    "        n = len(grid)\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        def dfs(x, y, prev):\n",
    "            if prev == n * n - 1:\n",
    "                return True\n",
    "            # print(\"prev = \", prev)\n",
    "            for i in range(0, n):\n",
    "                for j in range(0, n):\n",
    "                    if grid[i][j] == prev + 1:\n",
    "                        if abs((i - x) * (j - y)) == 2:\n",
    "                            return dfs(i, j, prev + 1)\n",
    "                        else:\n",
    "                            return False\n",
    "        return dfs(0, 0, 0)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        def dfs(x, y):\n",
    "            if grid[x][y] == bound:\n",
    "                return True\n",
    "            for (i, j) in [(x-2,y-1), (x-2, y+1), (x-1, y-2), (x-1, y+2), (x+1, y-2), (x+1, y+2), (x+2, y-1), (x+2, y+1)]:\n",
    "                if i >= 0 and i < n and j >= 0 and j < n and grid[i][j] == grid[x][y] + 1:\n",
    "                    return dfs(i, j)\n",
    "            return False\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        bound = n * n - 1\n",
    "        return dfs(0, 0)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        # 骑士必须从左上角出发，即grid[0][0]必须为0，否则返回False\n",
    "        if grid[0][0]:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        dist = [[2,1],[2,-1],[1,2],[1,-2],[-1,2],[-1,-2],[-2,1],[-2,-1]]\n",
    "        nums = [None] * n * n\n",
    "        for i,value_i in enumerate(grid):\n",
    "            for j,value_j in enumerate(grid[i]):\n",
    "                nums[grid[i][j]] = [i,j]\n",
    "        \n",
    "        x,y = nums[0]\n",
    "        for a,b in nums[1:]:\n",
    "            dist_x,dist_y = a-x,b-y\n",
    "            if [dist_x,dist_y] in dist:\n",
    "                x,y = a,b\n",
    "            else:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        count=0\n",
    "        n=len(grid)\n",
    "        def find(l, elem):\n",
    "            for row, i in enumerate(l):\n",
    "                try:\n",
    "                    column = i.index(elem)\n",
    "                except ValueError:\n",
    "                    continue\n",
    "                return row, column\n",
    "        row,col=find(grid,0)\n",
    "        if row!=0 or col!=0:\n",
    "            return False\n",
    "        for i in range(1,n*n):\n",
    "            count+=1\n",
    "            row_new,col_new=find(grid,count)\n",
    "            if abs(row_new-row)+abs(col_new-col)!=3 or abs(row_new-row)==3 or abs(col_new-col)==3:\n",
    "                return False\n",
    "            row=row_new\n",
    "            col=col_new\n",
    "        return True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        \n",
    "        n = len(grid)\n",
    "        if n==3:\n",
    "            return False\n",
    "        \n",
    "        coord = {}\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                coord[grid[i][j]] = (i, j)\n",
    "        \n",
    "        for i in range(1, n * n):\n",
    "            x1,y1 = coord[i]\n",
    "            x2,y2 = coord[i-1]\n",
    "            dx = abs(x1 - x2)\n",
    "            dy = abs(y1 - y2)\n",
    "            if dx * dy != 2:\n",
    "                return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        n=len(grid)*len(grid)\n",
    "        m=len(grid)\n",
    "        print(n)\n",
    "        if grid[0][0]!=0:return False\n",
    "        for i in range(m):\n",
    "            for j in range(m):\n",
    "                if grid[i][j]==0:\n",
    "                    row=i\n",
    "                    col=j\n",
    "                    break\n",
    "        print(row,col)\n",
    "        def check(r,c):\n",
    "            if r<0 or r>m-1 or c<0 or c>m-1: return -1\n",
    "            return grid[r][c]\n",
    "        for i in range(n-1):\n",
    "            if check(row+2,col+1)!=i+1 and check(row+1,col+2)!=i+1 and check(row-1,col+2)!=i+1 and check(row-2,col+1)!=i+1 and check(row-2,col-1)!=i+1 and check(row-1,col-2)!=i+1 and check(row+2,col-1)!=i+1 and check(row+1,col-2)!=i+1:\n",
    "                return False\n",
    "            if check(row+2,col+1)==i+1:\n",
    "                row += 2\n",
    "                col += 1\n",
    "            elif check(row+1,col+2)==i+1:\n",
    "                row += 1\n",
    "                col += 2\n",
    "            elif check(row+2,col-1)==i+1:\n",
    "                row += 2\n",
    "                col -= 1\n",
    "            elif check(row+1,col-2)==i+1:\n",
    "                row += 1\n",
    "                col -= 2\n",
    "            elif check(row-1,col-2)==i+1:\n",
    "                row -= 1\n",
    "                col -= 2\n",
    "            elif check(row-2,col-1)==i+1:\n",
    "                row -= 2\n",
    "                col -= 1\n",
    "            elif check(row-1,col+2)==i+1:\n",
    "                row -= 1\n",
    "                col += 2\n",
    "            elif check(row-2,col+1)==i+1:\n",
    "                row -= 2\n",
    "                col += 1\n",
    "        return True\n",
    "        #[8,3,6]\n",
    "        #[5,0,1]\n",
    "        #[2,7,4]\n",
    "        \n",
    "        #[24,11,22,17,4]\n",
    "        #[21,16,5,12,9]\n",
    "        #[6,23,10,3,18]\n",
    "        #[15,20,1,8,13]\n",
    "        #[0,7,14,19,2]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        arr = [[0, 0] for _ in range(n*n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                arr[grid[i][j]] = [i, j]\n",
    "        \n",
    "        for i in range(1, n*n):\n",
    "            row = abs(arr[i][0] - arr[i-1][0])\n",
    "            col = abs(arr[i][1] - arr[i-1][1])\n",
    "            if 1 <= row <= 2 and 1<= col <= 2 and abs(row-col) == 1:\n",
    "                continue\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        arr = [[0, 0] for _ in range(n*n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                arr[grid[i][j]] = [i, j]\n",
    "        \n",
    "        for i in range(1, n*n):\n",
    "            row = abs(arr[i][0] - arr[i-1][0])\n",
    "            col = abs(arr[i][1] - arr[i-1][1])\n",
    "            if abs(row-col) != 1 or min(row, col) != 1:\n",
    "                return False\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        self.final = m * n - 1\n",
    "        directions = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]\n",
    "        self.valid = False\n",
    "\n",
    "        def dfs(x, y, cnt):\n",
    "            if x < 0 or x >= m or y < 0 or y >= n:\n",
    "                return \n",
    "            if grid[x][y] != cnt:\n",
    "                return \n",
    "            if grid[x][y] == self.final:\n",
    "                self.valid = True\n",
    "                return \n",
    "            for xx, yy in directions:\n",
    "                dfs(x + xx, y + yy, cnt + 1)\n",
    "\n",
    "        dfs(0, 0, 0)\n",
    "        return self.valid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        position=[[] for _ in range(len(grid)**2)]\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid)):\n",
    "                position[grid[i][j]]=[i,j]\n",
    "        for i in range(len(position)):\n",
    "            if i==0:\n",
    "                if position[i]==[0,0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                if abs(position[i][0]-position[i-1][0])==2 and abs(position[i][1]-position[i-1][1])==1:\n",
    "                    continue\n",
    "                elif abs(position[i][1]-position[i-1][1])==2 and abs(position[i][0]-position[i-1][0])==1:\n",
    "                    continue\n",
    "                else:\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        visited=[[0]*m for _ in range(n)]\n",
    "\n",
    "        def ifValid(i,j):\n",
    "            return 0<=i<m and 0<=j<n and visited[i][j]==0\n",
    "\n",
    "        def dfs(i,j,step):\n",
    "            if step==m*n:\n",
    "                return True\n",
    "            directs=([i+2,j-1],[i+1,j-2],[i-1,j-2],[i-2,j-1],[i-2,j+1],[i-1,j+2],[i+1,j+2],[i+2,j+1])\n",
    "            for direct in directs:\n",
    "                x,y=direct[0],direct[1]\n",
    "                if ifValid(x,y) and grid[x][y]==step:\n",
    "                    # 选择节点\n",
    "                    step+=1   \n",
    "                    visited[x][y]=1\n",
    "\n",
    "                    if dfs(x,y,step):\n",
    "                        return True\n",
    "                    \n",
    "                    # 撤销选择\n",
    "                    step-=1\n",
    "                    # visited[x][y]=0\n",
    "\n",
    "            # 对于dfs没有遍历完所有节点的情况，返回False\n",
    "            return False\n",
    "\n",
    "        visited[0][0]=1\n",
    "        return dfs(0,0,1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:\n",
    "            return False\n",
    "        n = len(grid)\n",
    "\n",
    "        def dfs(i, j, idx):\n",
    "            if idx == n * n - 1:\n",
    "                return True\n",
    "            for r, c in [(i-1,j-2),(i-2,j-1),(i-2,j+1),(i-1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j-1),(i+1,j-2)]:\n",
    "                if 0 <= r < n and 0 <= c < n and grid[r][c] == idx + 1:\n",
    "                    if dfs(r, c, idx + 1):\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return dfs(0, 0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        def check(x,y,idx):\n",
    "            if idx == n*n:\n",
    "                return True\n",
    "            if x<0 or x>=n or y<0 or y>=n or grid[x][y]!=idx:\n",
    "                return False\n",
    "            for (dx,dy) in steps:\n",
    "                if check(x+dx,y+dy,idx+1): return True\n",
    "            return False\n",
    "\n",
    "\n",
    "        steps = [[-2,-1],[-2,1],[-1,-2],[-1,2],[2,1],[2,-1],[1,2],[1,-2]]\n",
    "        n = len(grid)\n",
    "        return check(0,0,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        if grid[0][0] != 0:#骑士会从棋盘的 左上角 出发\n",
    "            return False\n",
    "        n = len(grid)\n",
    "        indices = [[] for _ in range(n * n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                indices[grid[i][j]] = [i, j]\n",
    "        print(indices)\n",
    "        for i in range(1, n * n, 1):\n",
    "            dx = abs(indices[i][0] - indices[i - 1][0])\n",
    "            dy = abs(indices[i][1] - indices[i - 1][1])\n",
    "            if dx *dy!=  2:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkValidGrid(self, grid: List[List[int]]) -> bool:\n",
    "        t =len(grid)\n",
    "\n",
    "        def dfs(i: int, j: int, d: int):\n",
    "            if d == t*t:\n",
    "                return True\n",
    "            if grid[i][j] == d:\n",
    "                return dfs(i, j, d+1)\n",
    "\n",
    "            if i+2 <= t-1 and j+1 <= t-1 and grid[i+2][j+1]==d:  \n",
    "                return dfs(i+2, j+1, d+1)\n",
    "\n",
    "            elif i+2 <= t-1 and j-1 >= 0 and grid[i+2][j-1]==d:\n",
    "                return dfs(i+2, j-1, d+1)\n",
    "\n",
    "            elif i-2 >= 0 and j+1 <= t-1 and grid[i-2][j+1]==d:\n",
    "                return dfs(i-2, j+1, d+1)\n",
    "\n",
    "            elif i-2 >= 0 and j-1 >= 0 and grid[i-2][j-1]==d:\n",
    "                return dfs(i-2, j-1, d+1)\n",
    "\n",
    "            elif i-1 >= 0 and j+2 <= t-1 and grid[i-1][j+2]==d:\n",
    "                return dfs(i-1, j+2, d+1)\n",
    "\n",
    "            elif i-1 >= 0 and j-2 >= 0 and grid[i-1][j-2]==d:\n",
    "                return dfs(i-1, j-2, d+1)\n",
    "                \n",
    "            elif i+1 <= t-1 and j+2 <= t-1 and grid[i+1][j+2]==d:\n",
    "                return dfs(i+1, j+2, d+1)\n",
    "                \n",
    "            elif i+1 <= t-1 and j-2 >=0 and grid[i+1][j-2]==d:\n",
    "                return dfs(i+1, j-2, d+1)\n",
    "            return False\n",
    "                \n",
    "        return dfs(0,0,0)\n",
    "                 "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
